package com.gali.leetcode.day18;

/**
 * @Auther: gali
 * @Date: 2022-08-04 20:25
 * @Description:
 */
public class Solution {
    /**
     * 不同路径---动态规划
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int f[][]=new int[m][n];
        for (int i = 0; i < m; i++) {
            f[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            f[0][i]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }


    /**
     * 不同路径 II----动态规划  滚动数组
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int f[]=new int[m];
        f[0]=obstacleGrid[0][0]==0?1:0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j]==1){
                    //是障碍物
                    f[j]=0;
                    continue;
                }
                if (j-1>=0&&obstacleGrid[i][j-1]==0){
                    f[j]+=f[j-1];
                }
            }
        }
        return f[m-1];
    }
}
